package org.yagnus.stats.sampler.discrete.withreplacement;

import java.util.Random;

import java.util.TreeMap;

import org.yagnus.datastructure.TotallyOrderedRange;

import org.yagnus.stats.sampler.disrete.Utils;

/**
 *
 * @author Hsb
 *
 * This implementation of the Array sampler uses a TreeMap that maps number ranges (as implemented by TotallyOrderedRange
 *  that span the real segment [0,1] to the object corresponding to that range.
 *
 * Construct time: O(nlgn) to construct the tree.
 * Draw time: O(1), O(lgn), O(n); (best, amortized, worst)
 * Update time: When implemented, adding/removing an item should take O(lgn) on average
 * Bulk draw: O(dlgn)
 * Memory: O(n)
 *
 * Where n is the size of the population, and d is the number of draws that we make.
 *
 * TODO: A more sophisticated algorithm would use a Tree optimized for each distribution.
 * TODO: write the updates to sample space
 *
 * @param <BASETYPE> the type of stuff we're sampling from
 *
 * 
 */
public class TreeArraySampler<BASETYPE> extends WithReplacementSampler<BASETYPE> {

    TreeMap<TotallyOrderedRange, BASETYPE> map;

    @Override
    protected void _init(BASETYPE[] t, double[] weights) {

        map = new TreeMap<TotallyOrderedRange, BASETYPE>();

        if (t.length != weights.length) {
            throw new IllegalArgumentException("The sample space and the input probability are not same length.");
        }
        double[] ps = Utils.makeProbability(weights, 0);

        double sum = 0, nextv;
        for (int i = 0; i < t.length; ++i) {
            if (t[i] == null) {
                throw new IllegalArgumentException("Sample space cannot contain null");
            }

            nextv = sum + ps[i];
            TotallyOrderedRange<Double> range = TotallyOrderedRange.getOpenRight(sum, nextv);
            map.put(range, t[i]);
            sum = nextv;
        }

    }

    public BASETYPE draw() {
        BASETYPE ret = null;
        do {
            ret = map.get(TotallyOrderedRange.getPoint(rng().nextDouble()));
        } while (ret == null);
        return ret;
    }

    public TreeArraySampler(BASETYPE[] t, double[] weights) {
        super(t, weights);
    }

    public TreeArraySampler(BASETYPE[] t, long[] weights) {
        super(t, weights);
    }

    public TreeArraySampler(BASETYPE[] t, int[] weights) {
        super(t, weights);
    }

    public TreeArraySampler(BASETYPE[] t) {
        super(t);
    }

    @Override
    public void addSample(BASETYPE t, double w) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public void removeSample(BASETYPE t) {
        throw new UnsupportedOperationException("Not supported yet.");
    }
}
